Implementacija Deficit Round Robin algoritma kod svičeva sa baferima na izlazu
Vrsta: Seminarski | Broj strana: 32 | Nivo: Elektrotehnički fakultet

Apstrakt
Cilj rada je ispitivanje performansi arhitekture rutera sa baferima na izlazu, realizacijom saobraćaja sa rezervacijama i best-effort saobraćaja. Obrada paketa unutar rutera vrši se po Deficit Round Robin (DRR) algoritmu. Prikazane su osnovne performanse ove arhitekture: kašnjenje i fer servis. U okviru realizacije saobracaja sa rezervacijama analizirano je kašnjenje kroz ruter, dok je u okviru realizacije best – effort saobraćaja pokazano u kojoj meri može biti zadovoljen fer servis. Na osnovu rezultata simulacije potvrđeno je da se ovakvom arhitekturom svakom korisniku može garantovati kašnjenje i fer servis.
Uvod
U računarskim mrežama, kao i svuda gde postoje resursi koji su ograničeni, od velikog je značaja ravnopravna podela tih resursa. Ruteri imaju bafere koji su fiksne dužine, dolazni i odlazni linkovi su ograničenog kapaciteta, tako da je vrlo bitno obezbediti njihovu raspodelu na optimalan način za svakog korisnika ponaosob. Međutim, u velikom broju računarskih mreža dešava se da agresivni korisnici, koji šalju veliku količinu podataka sa nekontrolisanim protokom, zauzmu značajan deo bafera u ruteru. Ovo rezultuje time da ostali korisnici, uslovno rečeno “neagresivni”, mogu biti odbijeni, a protok njihovih podataka značajno smanjen. Ovakav problem posebno je izražen kod rutera koji koriste FCFS (First-Come-First-Serve) algoritam za opsluživanje paketa.
Potrebno je definisati kriterijum mere fer servisa u mreži kao i algoritam koji bi to podržao. Motivacija za stvaranje algoritma kojim se ostvaruje fer servis jeste postizanje fer podele resursa i ostvarivanje veće brzine protoka. Intuitivno usluga je fer ukoliko nijedan korisnik ne dobija više nego sto je tražio, a svaki eventualni višak se ravnomerno raspodeli. U literaraturi postoji nekoliko definicija fer servisa. Rad se zasniva na definiciji po kojoj je bit-by-bit Round Robin (BR) algoritam apsolutno fer. U svakom prolasku kroz BR algoritam, svaki tok u kome ima paketa opslužuje se minimalno koliko se može opslužiti, odnosno jedan bit. Ukoliko neki korisnik ima veći prioritet, on će biti opslužen srazmerno težini wi koja mu je dodeljena, odnosno wi bita u svakom prolasku.
BR predstavlja apsolutno fer algoritam, ali to je teorijski protokol i vrlo ga je teško implementirati. Stoga se koristi DRR algoritam, kojim se ostvaruje skoro idealan fer servis i jednostavan je za implementaciju. Sledi prikaz osnovnih koncepta DRR algoritma.
Na Sl.1 prikazana je šema na kojoj se zasniva mehanizam rada DDR. Šema se sastoji iz prihvatnog bafera, redova za čekanje po tokovima i izlaznog bafera. Paketi različitih korisnika dolaze u ruter, smeštaju se u prihvatni bafer i raspoređuju se u redove za čekanje po tokovima (enqueing). Na osnovu izvorišne i odredišne IP adrese paketa određuje se kom redu za čekanje, odnosno toku pripadaju. Zatim se tokovi opslužuju po DRR algoritmu i obrađeni paketi šalju na izlazni link.

---------- CEO RAD MOŽETE PREUZETI NA SAJTU. ---------- 

www.maturski.org 

 

MOŽETE NAS KONTAKTIRATI NA E-MAIL: [email protected]